from Interface.Map import Map


class HashMap(Map):
    class LinkedListNode:
        def __init__(self, key, value):
            self.key = key
            self.value = value
            self.next = None

    def __init__(self,_capacity: int = 17):
        self._capacity = _capacity if _capacity > 17 else 17
        self.size = 0
        self.rbt_threshold = 8   # 临界因子,单链表转化成红黑树的阈值
        self.link_threshold = 6  # 临界因子，红黑树还原成单链表的阈值----经过remove方法，长度下降到6开始
        self.buckets = [None] * self._capacity

    def __len__(self):
        return self.size

    @staticmethod
    def hash(self, key):
        return hash(key)%self._capacity

    # @Overrides
    def put(self, key, value):
        index = self.hash(self, key)
        if self.buckets[index] is None:
            self.buckets[index] = self.LinkedListNode(key, value)
        else:
            cur = self.buckets[index]
            while cur.next is not None:
                cur = cur.next
            cur.next = self.LinkedListNode(key, value)
        self.size += 1

    # @Overrides
    def get(self, key):
        index = HashMap.hash(self, key)
        if self.buckets[index] is None:
            return None
        else:
            cur = self.buckets[index]
            while cur is not None:
                if cur.key == key:
                    return cur.value
            else:
                return None

    # @Overrides
    def remove(self, key):
        index = HashMap.hash(self, key)
        if self.buckets[index] is None:
            return None
        else:
            cur = self.buckets[index]
            parent = None
            while cur is not None:




